home *** CD-ROM | disk | FTP | other *** search
/ Oh!X 2001 Spring / Oh!X 2001 Spring Special CD-ROM (Japan).7z / Oh!X 2001 Spring Special CD-ROM (Japan) (Track 1).bin / PUZZLE / puz01 / ms2.c < prev    next >
C/C++ Source or Header  |  2000-02-20  |  3KB  |  149 lines
  1. /*
  2.  * ms2.c : マジックスター全解探索
  3.  *
  4.  *               Copyright (C) 2000 by Makoto Hiroi
  5.  *
  6.  */
  7.  
  8. /*
  9.         パズルの内容
  10.  
  11.                 ０
  12.               ／  ＼
  13.     １------２------３------４
  14.       ＼  ／          ＼  ／             
  15.         ５              ６
  16.       ／  ＼          ／  ＼
  17.     ７------８------９------10
  18.               ＼  ／  
  19.                 11
  20.  
  21.     1 - 12 の数字を入れて
  22.     直線上にある４つの数字の和が
  23.     全て 26 になるようにする
  24.  
  25.     0-2-5-7, 0-3-6-10, 7-8-9-10
  26.     1-2-3-4, 1-5-8-11, 4-6-9-11
  27. */
  28.  
  29. #include <stdio.h>
  30. #include <stdlib.h>
  31. #include <string.h>
  32. #include <time.h>
  33.  
  34. #define TRUE  1
  35. #define FALSE 0
  36. #define N     12
  37. #define LINE  6
  38.  
  39. const char line[LINE][4] = {
  40.   0, 2, 5, 7,  0, 3, 6, 10,  7, 8, 9, 10,
  41.   1, 2, 3, 4,  1, 5, 8, 11,  4, 6, 9, 11
  42. };
  43.  
  44. const char postion_line[N][2] = {
  45.   0, 1,  /* 0 */
  46.   3, 4,  /* 1 */
  47.   0, 3,  /* 2 */
  48.   1, 3,  /* 3 */
  49.   3, 5,  /* 4 */
  50.   0, 4,  /* 5 */
  51.   1, 5,  /* 6 */
  52.   0, 2,  /* 7 */
  53.   2, 4,  /* 8 */
  54.   2, 5,  /* 9 */
  55.   1, 2,  /* 10 */
  56.   4, 5,  /* 11 */
  57. };
  58.  
  59. int total[LINE];         /* 合計 */
  60. int number_count[LINE];  /* 数字を置いた個数 */
  61.  
  62. char star[N];
  63. char use_number[N + 1];
  64. int  count = 0;
  65.  
  66. /* 出力 */
  67. void print_star( void )
  68. {
  69.   int i;
  70.   for( i = 0; i < N; i++ ){
  71.     printf("%2d ", star[i] );
  72.   }
  73.   printf("\n");
  74. }
  75.  
  76. /* 数値のセット */
  77. int set_number( int pos, int num )
  78. {
  79.   int i;
  80.   for( i = 0; i < 2; i++ ){
  81.     int line = postion_line[pos][i];
  82.     if( number_count[line] == 3 && total[line] + num != 26 ){
  83.       return FALSE;
  84.     }
  85.   }
  86.   for( i = 0; i < 2; i++ ){
  87.     int line = postion_line[pos][i];
  88.     total[line] += num;
  89.     number_count[line]++;
  90.   }
  91.   use_number[num] = TRUE;
  92.   star[pos] = num;
  93.   return TRUE;
  94. }
  95.  
  96. /* 数字の削除 */
  97. void remove_number( int pos, int num )
  98. {
  99.   int i;
  100.   for( i = 0; i < 2; i++ ){
  101.     int line = postion_line[pos][i];
  102.     total[line] -= num;
  103.     number_count[line]--;
  104.   }
  105.   use_number[num] = FALSE;
  106.   star[pos] = FALSE;
  107. }
  108.  
  109. /* 探索 */
  110. void search_star( int pos )
  111. {
  112.   if( pos == N ){
  113.     count++;
  114.     print_star();
  115.   } else {
  116.     int n;
  117.     for( n = 1; n <= N; n++ ){
  118.       if( !use_number[n] && set_number( pos, n ) ){
  119.     search_star( pos + 1 );
  120.     remove_number( pos, n );
  121.       }
  122.     }
  123.   }
  124. }
  125.  
  126. /* 初期化 */
  127. void init_global( void )
  128. {
  129.   int i;
  130.   memset( use_number, 0, N + 1 );    /* 初期化 */
  131.   for( i = 0; i < LINE; i++ ){
  132.     total[i] = 0;
  133.     number_count[i] = 0;
  134.   }
  135. }
  136.  
  137. int main()
  138. {
  139.   int start, end;
  140.   init_global();
  141.   start = clock();
  142.   search_star( 0 );
  143.   end = clock();
  144.   printf("総数 %d 個, 時間 %d\n", count, end - start );
  145.   return 0;
  146. }
  147.  
  148. /* end of file */
  149.